import java.util.Arrays;
public class MergeSort {

    public static void mergeSort(int[] array){
        mergeSortFunc1(array,0,array.length-1);
    }
    public static void mergeSortFunc1(int[]array,int left,int right){
        //开始先分割
        if(left>=right){
            return ;
        }
        int mid=(left+right)/2;
        //递归左区间和递归右区间分割
        mergeSortFunc1(array,left,mid);
        mergeSortFunc1(array,mid+1,right);
        //分割后合并
        merge(array,left,mid,right);

    }
     // 合并原理：合并两个有序数组
    public static void merge(int[]array,int start,int mid,int end){

        //先分别找出两个数组中第一个更小的元素，将更小的元素搬到
        //额外空间
        int[] extra=new int[end-start+1];

        int i=start;
        int j=mid+1;
        int k=0;
        //两个数组都还有元素时
        while(i<=mid&&j<=end){
            if(array[i]<=array[j]){
                 extra[k++]=array[i++];
            }else {
                extra[k++] = array[j++];
            }
        }
        //当有一个数组已经搬完时，需要判断哪个数组搬完了
        while(i<=mid){
            //把没有搬完的数组全部搬到额外数组
            extra[k++]=array[i++];
        }
        while(j<=end){
            //把没有搬完的数组全部搬到额外数组
          extra[k++]=array[j++];
        }
        //全部搬到额外空间时，再搬回原数组

        for(int n=0;n<extra.length;n++){
            //原来的数组不一定是从零开始
            array[start+n]=extra[n];
        }
    }
//简单测试
    public static void main(String[] args) {
        int[] array={1,5,1,0,6,88,-5,0,64};
        mergeSort(array);
        System.out.println(Arrays.toString(array));

    }
}
